public class QuickSortJava {

    public static void main(String[] args) {
        

        int[] arr = {10,7,2,4,7,62,3,4,2,1,8,9,19};
        quickSort(arr, 0, arr.length-1);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+ " ");
        }


    }

    private static void quickSort(int[] arr, int left, int right){

        //快排
        if(left > right) return;

        //哨兵
        int i = left, j = right;

        //交换变量
        int t;

        //基准
        int temp = arr[i];

        while (i < j) {
            
            //右边哨兵依次递减，直到发现比基准小的数
            while (temp <= arr[j] && i < j) {
                
                j--;

            }

            //左边哨兵依次增加，直到发现比基准大的数

            while (temp >=arr[i] && i < j) {
        
                i++;

            }

            if(i < j){

                //满足条件，交换
                t = arr[j];
                arr[j] = arr[i];
                arr[i] = t;
            }

        }

        //最后将基准和 ij 遇到的值兑换
        arr[left] = arr[i];
        arr[i] = temp;

        //递归
        quickSort(arr, left, j-1);
        quickSort(arr, j+1, right);


    }
}